package Random._528_RandomPickwithWeight;

import java.util.Random;

public class Solution {
    int[] totalWeights;
    int total;
    public Solution(int[] w) {
        this.totalWeights = new int[w.length + 1];
        this.total = 0;
        for (int i = 0; i < w.length; i++) {
            total += w[i];
            totalWeights[i + 1] = total;
        }
    }

    public int pickIndex() {
        Random r = new Random();
        int val = r.nextInt(total) + 1;
        int pos = 0;
        for (int i = 1; i <= totalWeights.length; i++) {
            if (totalWeights[i - 1] < val && val <= totalWeights[i]) {
                pos = i - 1;
                break;
            }
        }
        return pos;
    }
}
